# Definition for singly-linked list.

from queue import PriorityQueue
from typing import List

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

# 可能是因为元组的原因，超时了
class Solution:

    def __init__(self):
        self.index = 0

    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        heap = self.__queuify(lists)

        head, tail = None, None
        while len(lists) > 0:
            (_, _, node) = heap.get()
            if head == None:
                head = node
                tail = node
            else:
                tail.next = node
                tail = tail.next
            nnext = node.next
            if nnext != None:
                heap.put((nnext.val, self.__incrAndGetIndex(), nnext))
        return head

    def __incrAndGetIndex(self):
        self.index += 1
        return self.index

    def __queuify(self, lists: List[ListNode]):
        q = PriorityQueue(len(lists))
        for node in lists:
            q.put((node.val, self.__incrAndGetIndex(), node))
        return q